package chapter02;

public class IsSameTree100 {
    /**
     * 深度优先搜索
     * process(xNode,yNode) 以xNode和yNode为头的两颗树是否完全相同
     * 递归出口
     *  1).xNode==null&&yNode==null
     *      return true
     *  2).xNode==null&&yNode!=null||xNode!=null&&yNode==null||xNode.val!=yNode.val
     *      return false
     *  3).判断左 右子树是否完全相同
     *      return process(xNode.left,yNode.left)&&process(xNode.right,yNode.right)
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
        }
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if(p==null&&q!=null||p!=null&&q==null){
            return false;
        }
        return process(p,q);
    }

    public boolean process(TreeNode xNode,TreeNode yNode){
        if(xNode==null&&yNode==null){
            return true;
        }else if(xNode==null&&yNode!=null||xNode!=null&&yNode==null){
            return false;
        }else if(xNode.val!=yNode.val){
            return false;
        }else{
            return process(xNode.left,yNode.left)&&process(xNode.right,yNode.right);
        }
    }
}
